#! /usr/bin/env python
# -*- coding: utf-8 -*-


class Solution:
    """
    @param: matrix: an integer matrix
    @return: the coordinate of the left-up and right-down number
    """
    def submatrixSum(self, matrix):
        ''' self.accu 为当前节点到[1,1]的子矩阵之和: accumulation
            trick:　self.accu下标从1开始处理, 这样0行0列可以存放0, 消除了边界判断

            rd : right-down
            lu : left-up
        '''
        self.matrix = matrix
        self.rows, self.cols = len(matrix), len(matrix[0])

        one_row_accu = [0] * (self.cols+1)
        self.accu = [list(one_row_accu) for i in range(self.rows+1)]
        # self.accu = [one_row_accu for i in range(self.rows+1)]        # NOTE: 这里不能深度拷贝

        for rd_row in range(1, self.rows + 1):
            for rd_col in range(1, self.cols+1):
                self.calc_accu(rd_row, rd_col)
                value = self.find_0_sub_mat(rd_row, rd_col)
                if value:
                    return value

        # print(self.accu)

    def calc_accu(self, rd_row, rd_col):
        # self.accu[rd_row][rd_col] = ele + self.accu[rd_row-1][rd_col] + self.accu[rd_row][rd_col-1] - self.accu[rd_row-1][rd_col-1]
        ele     = self.matrix[rd_row-1][rd_col-1]
        up      = self.accu[rd_row-1][rd_col]
        left    = self.accu[rd_row][rd_col-1]
        up_left = self.accu[rd_row-1][rd_col-1]

        value = ele + (up + left - up_left)
        self.accu[rd_row][rd_col] = value
        return value

    def calc_sub_mat_sum(self, lu_row, lu_col, rd_row, rd_col):
        up               = self.accu[lu_row-1][rd_col]
        left             = self.accu[rd_row][lu_col-1]
        up_left          = self.accu[lu_row-1][lu_col-1]
        complete_sub_mat = self.accu[rd_row][rd_col]

        return complete_sub_mat - up - left + up_left

    def find_0_sub_mat(self, rd_row, rd_col):
        for lu_row in range(1, rd_row+1):
            for lu_col in range(1, rd_col+1):
                value = self.calc_sub_mat_sum(lu_row, lu_col, rd_row, rd_col)
                if value == 0:
                    return [(lu_row-1, lu_col-1), (rd_row-1, rd_col-1)]
        return None


class Solution_slow:
    """
    @param: matrix: an integer matrix
    @return: the coordinate of the left-up and right-down number
    """

    def submatrixSum(self, matrix):
        self.matrix = matrix
        one_row = matrix[0]
        self.rows, self.cols = len(matrix), len(one_row)
        self.sum_cache = {}     # row and col's diagonal : sum

        for row_slice in self.slice_generator(self.rows):
            for col_slice in self.slice_generator(self.cols):
                r = self.sum_optimize(row_slice, col_slice)

                if r == 0:
                    # 返回找到的第一个值
                    result = self.diagonal(row_slice, col_slice)
                    return list(result)

    # def sum(self, row_slice, col_slice):
    #     ''' 裸算, 不带任何优化, 每次都把此子矩阵中元素重新计算一次
    #     '''
    #     result = 0
    #     col_begin, col_end = col_slice

    #     for row in range(*row_slice):
    #         row_values = self.matrix[row]
    #         result += sum( row_values[col_begin:col_end] )

    #     print(row_slice, col_slice, result)
    #     return result

    def sum_optimize(self, row_slice, col_slice):
        diagonal = self.diagonal(row_slice, col_slice)
        is_cached, sum = self.is_cached(diagonal)

        if is_cached:
            return sum

        row_begin, row_end = row_slice
        col_begin, col_end = col_slice

        if row_begin+1 == row_end:
            # 只有一行时: 列分治
            if col_begin+1 == col_end:
                assert False, '不可能, 矩阵中的元素会先命中缓存'
                return self.matrix[row_begin][col_begin]
            else:
                left_slice, right_slice = self.slice_divide(col_slice)
                sum = self.sum_optimize(row_slice, left_slice) + self.sum_optimize(row_slice, right_slice)
        else:
            # 行分治
            up_slice, down_slice = self.slice_divide(row_slice)
            sum = self.sum_optimize(up_slice, col_slice) + self.sum_optimize(down_slice, col_slice)

        self.sum_cache[diagonal] = sum
        return sum

    def is_cached(self, diagonal):
        left_up, bottom_down = diagonal

        if left_up == bottom_down:
            # 命中矩阵中的元素
            row, col = left_up
            return True, self.matrix[row][col]

        if diagonal in self.sum_cache:
            # 命中曾经计算过的两个对角
            # print('hit cache diagonal %s' % str(diagonal))
            return True, self.sum_cache[diagonal]

        return (False, -1)

    @staticmethod
    def slice_generator(max):
        # 从0 开始
        for begin in range(max):
            for end in range(begin+1, max+1):
                yield begin, end        # [begin, end)

    @staticmethod
    def slice_divide(slice):
        begin, end = slice
        assert begin + 1 < end, "只有一个元素切分无意义, 但可以更改"

        mid = (begin + end) // 2
        return  (begin, mid), (mid, end)

    @staticmethod
    def diagonal(row_slice, col_slice):
        # 获取对角: 左上 + 右下
        row_begin, row_end = row_slice
        col_begin, col_end = col_slice
        left_up     = (row_begin, col_begin)
        bottom_down = (row_end-1, col_end-1)

        return (left_up, bottom_down)

def main():
    from numpy import array
    from time import time

    print("start main")
    s = Solution()
    # r = s.slice_generator(1)
    # r = s.slice_generator(2)
    # r = list(r)

    matrix = [
        [1,5,7],
        [3,7,-8],
        [4,-8,9]
    ]

    # matrix = [
    #     [0,4],
    #     [-4,0]
    # ]

    from m8 import data
    matrix = data

    # matrix = array([
    #     [1,2,3],
    #     [4,5,6],
    # ])

    begin = time()
    r = s.submatrixSum(matrix)
    print(r)

    print(time() - begin)

if __name__ == "__main__":
    main()
